//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 算法的时间复杂度应该为 O(log (m+n)) 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -10⁶ <= nums1[i], nums2[i] <= 10⁶ 
// 
//
// Related Topics 数组 二分查找 分治 👍 7651 👎 0

import enums.Way;

/**
 * 寻找两个正序数组的中位数
 */
class FindMedianSortedArrays {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2, Way way) {
        switch (way){
            case WAY1:
                return way1(nums1, nums2);
            case WAY2:
                return way2(nums1, nums2);
            case WAY3:
                return way3(nums1, nums2);
            default:
                throw new IllegalArgumentException("Way is not exist.");
        }

    }

    /**
     * 合并两个数组
     * 时间复杂度O(m+n)
     * 空间复杂度O(m+n)
     */
    private static double way1(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] temp = new int[m + n];
        for (int i = 0; i < m; i++) {
            temp[i] = nums1[i];
        }
        for (int j = 0; j < n; j++) {
            temp[m + j] = nums2[j];
        }

        for (int i = 0; i < temp.length; i++) {
            for (int j = i + 1; j < temp.length; j++) {
                if (temp[i] > temp[j]) {
                    int temp1 = temp[i];
                    temp[i] = temp[j];
                    temp[j] = temp1;
                }
            }
        }
        if ((m + n) % 2 == 0) {
            return (temp[(m + n) / 2] + temp[(m + n) / 2 - 1]) / 2.0;
        } else {
            return temp[(m + n) / 2];
        }
    }

    /**
     * 双指针
     * 时间复杂度O(log(m+n))
     * 空间复杂度O(1)
     */
    private static double way2(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int mid = (m + n) / 2;
        int curr = 0, prev = 0;
        int i = 0, j = 0;
        for (int c = 0; c <= mid; c++) {
            prev = curr;
            if (i < m && (j >= n || nums1[i] < nums2[j])) {
                curr = nums1[i++];
            } else {
                curr = nums2[j++];
            }
        }
        if ((m + n) % 2 == 0) {
            return (curr + prev) / 2.0;
        } else {
            return curr;
        }
    }

    /**
     * 二分查找法
     * 时间复杂度O(log(min(m, n)))
     * 空间复杂度O(1)
     */
    private static double way3(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return way3(nums2, nums1);
        }
        int m = nums1.length, n = nums2.length;
        int total = m + n;
        int half = (total + 1) / 2;
        int left = 0, right = m;
        while (left <= right) {
            int i = left + (right - left) / 2;
            int j = half - i;

            int L1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int R1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int L2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int R2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
            if (L1 <= R2 && L2 <= R1) {
                if (total % 2 == 1) {
                    return Math.max(L1, L2);
                } else {
                    return (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0;
                }
            } else if (L1 > R2) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }
        throw new IllegalArgumentException("Arrays are not sorted.");
    }
}